#include "stack_queue.h"

void MyStack::printStack() {
	listNode* p = topNode;

	while (p != NULL) {
		if (p->next == NULL)
			cout << p->data << endl;
		else
			cout << p->data << ",";

		p = p->next;

	}
}

void MyQueue::printQueue() {
	int cursor = front;

	while (cursor != rear) {
		if ((cursor + 1) % capacity == rear)
			cout << queue[cursor] << endl;
		else
			cout << queue[cursor] << ",";

		cursor = (cursor + 1) % capacity;
	}
}

MyStack::MyStack() {
	topNode = NULL;
	stackSize = 0;
}

MyStack::~MyStack() {
	listNode* l = topNode;
	while (topNode) {
		topNode = topNode->next;
		delete l;
		l = topNode;
	}
	stackSize = 0;
}

bool MyStack::isEmpty() {
	if (stackSize == 0) return true;
	else return false;
}

bool MyStack::push(const int& a) {
	listNode* j = new listNode;
	if (j == NULL) return false;
	else {
		j->data = a;
		j->next = topNode;
		topNode = j;
		stackSize++;
		return true;
	}
}

bool MyStack::pushch(const char& a) {
	listNode* j = new listNode;
	if (j == NULL) return false;
	else {
		j->ch = a;
		j->next = topNode;
		topNode = j;
		stackSize++;
		return true;
	}
}

bool MyStack::pop(int& item) {
	listNode* y = new listNode;
	if (stackSize == 0) return false;
	else {
		item = topNode->data;
		y = topNode;
		topNode = topNode->next;
		delete y;
		stackSize--;
		return true;
	}
}

bool MyStack::popch() {
	listNode* y = new listNode;
	if (stackSize == 0) return false;
	else {
		y = topNode;
		topNode = topNode->next;
		delete y;
		stackSize--;
		return true;
	}
}

bool MyStack::getTop(int& a) {
	if (stackSize == 0) return false;
	else {
		a = topNode->data;
		return true;
	}
}

bool MyStack::getTopch(char& c) {
	if (stackSize == 0) return false;
	else {
		c = topNode->ch;
		return true;
	}
}


MyQueue::MyQueue(const int&a) {
	capacity = a;
	front = rear = 0;
	queue = new int[capacity];
}

MyQueue::~MyQueue() {
	delete[] queue;
}

bool MyQueue::enQueue(const int&a) {
	if ((rear + 1) % capacity == front) return false;
	else {
		queue[rear] = a;
		rear = (rear + 1) % capacity;
		return true;
	}
}

bool MyQueue::deQueue(int& item) {
	if (front == rear) return false;
	else {
		item = queue[front];
		front = (front + 1) % capacity;
		return true;
	}
}

bool MyQueue::getFront(int& item) {
	if (front == rear) return false;
	else {
		item = queue[front];
		return true;
	}
}

int priority(char op) {
	int priority;
	if (op == '+' || op == '-') priority = 1;
	if (op == '*' || op == '/') priority = 2;
	if (op == '(') priority = 0;
	return priority;
}

bool postfixExpression(const string&a, string& result) {
	result ="";
	int n = 0;
	MyStack Sop;
	int len = a.length();
	char c;
	for (int i = 0; i < len; i++) {
		if (a[i] == '(') n++;
		if (a[i] == ')') n--;
	}
	if (n != 0) {
		result = "Expression is wrong!";
		return false;
	}
	for (int i = 0; i < len; i++) {
		if (a[i] >= '0' && a[i] <= '9') result += a[i];
		else {
			if (Sop.isEmpty() || a[i] == '(') {
				Sop.pushch(a[i]);
			} else if (a[i] == '(') {
				Sop.pushch(a[i]);
			} else if (a[i] == ')') {
				while (Sop.getTopch(c) && c != '(') {
					result += c;
					Sop.popch();
				}
				Sop.popch();
			} else {
				while (Sop.getTopch(c) && priority(a[i]) <= priority(c)) {
					result += c;
					Sop.popch();
					if (Sop.isEmpty()) break;
				}
				Sop.pushch(a[i]);
			}
		}
	}
	while (!Sop.isEmpty()) {
		Sop.getTopch(c);
		result += c;
		Sop.popch();
	}
	return true;
}

int calculate(char a,int c,int b){
	if(a=='+') return b+c;
	if(a=='-') return b-c;
	if(a=='*') return b*c;
	if(a=='/') return b/c;
	return 0;
}

bool expressionVal(const string& a, int& result) {
	string ans;
	MyStack opn;
	if(postfixExpression(a,ans)){
	postfixExpression(a, ans);
	int len = ans.length();
	for (int i = 0; i < len; i++) {
		if (ans[i] >= '0' && ans[i] <= '9') {
			int n = ans[i] - '0';
			opn.push(n);
		}
		else {
			int b,c;
			opn.pop(c);
			opn.pop(b);
			opn.push(calculate(ans[i],c,b));
		}
	}
	int num;
	opn.pop(num);
	result = num;
	return true;
	}
	else return false;
}

void yanghui(const int&n) {
	MyQueue mq(1000);
	int cur;
	int temp;
	mq.enQueue(0);
	mq.enQueue(1);
	mq.enQueue(0);
	for (int i = 1; i <= n + 1
	        ; i++) {
		for (int l = 0; l < i + 2; l++) {
			mq.deQueue(cur);
			if (cur == 0 && l == 0) {
				mq.enQueue(cur);
			}
			if (cur != 0 && i != 1) {
				if (l < i)
					cout << cur << ",";
				else cout << cur;
			}
			mq.getFront(temp);
			int x = temp + cur;
			mq.enQueue(x);

		}
		if (i != 1)
			cout << endl;
	}
}
